package Sorted;

import java.util.Comparator;

public class Sorts {
	public static <T extends Comparable<? super T>> void insertSort(T[] nums){
		int size=nums.length;
		
		for (int j,i=1;i<size;++i){
			j=i-1;
			T current=nums[i];
			while(j>0&&current.compareTo(nums[j])<0){
				nums[j+1]=nums[j];
				--j;
			}
			nums[j+1]=current;
		}
	}
	
	public static <T extends Comparable<? super T>> void quickSort(T[] nums){
		quickSort(nums,0,nums.length-1);
	}
	
	public static <T extends Comparable<? super T>> void quickSort(T[] nums,int start,int end){
		if (start>=end){
			return;
		}
		int i=start;
		int j=end;
		
		T key=nums[start];
		while(i<j){
			while (i<j&&nums[j].compareTo(key)<0){
				--j;
			}
			if (i<j)
				nums[i++]=nums[j];
			while (i<j&&nums[i].compareTo(key)>0){
				++i;
			}
			if(i<j)
				nums[j--]=nums[i];
		}
		nums[i]=key;
		quickSort(nums,start,j-1);
		quickSort(nums,j+1,end);
	}
}
